package algorithm.middle;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-02-10 13:44
 * @Description:给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *
 * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *
 * 示例1:
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 *
 *
 * 示例2:
 *
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CheckInclusion567 {
    public static void main(String[] args) {
        boolean b = checkInclusion("adc", "dcda");
        System.out.println(b);
    }
    //双指针
    public static boolean checkInclusion(String s1, String s2) {
        char[] chars = s1.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char x:chars){
            map.put(x,map.get(x)==null?1:map.get(x)+1);
        }
        int left = 0;
        int right = 0;
        char[] arr = s2.toCharArray();
        while(right<arr.length){
            map.get(arr[right]);
            if (map.get(arr[right])==null){
                while (map.get(arr[right])==null && left < right){
                    map.put(arr[left],map.get(arr[left])==null?1:map.get(arr[left])+1);
                    left++;
                }
                //如果跳出来的时候，左指针刚好移动到右指针，说明这个元素根本不在map里面，此时都向后挪动
                if (left==right){
                   right++;
                   left=right;
                   continue;
                }
            }
            if (map.get(arr[right])>1){
                map.put(arr[right],map.get(arr[right])-1);
            }else {
                map.remove(arr[right]);
            }
            if (map.size()==0){
                return true;
            }
            right++;
        }
        return false;
    }
    //滑动窗口
    //比较两个字典是否完全一致即可
    public boolean 官方思路(String s1, String s2){
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
        //cnt2此时为初始化之后的窗口
        for (int i = n; i < m; ++i) {
            ++cnt2[s2.charAt(i) - 'a'];
            --cnt2[s2.charAt(i - n) - 'a'];
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }
}
